package find.duplicate.subtrees;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @Time 2019/12/31
 * @author 王光浩
 * @Need 给出一个棵二叉树，找出二叉树上所有具有相同结构，且每一个节点值对应相等的子树，结果只需返回一个具有
 *       这种相同结构子树的根节点。
 * @Thingking 使用HashMap。定义一个HashMap，HashMap中key的值为中序遍历的值+前序遍历值的字符串。
 *            HashMap的value值固定为1，用于判断该节点是否存在过重复。
 *            
 *            思路：遍历二叉树，获取每一个节点的中序遍历值和前序遍历值 ，然后将前序遍历值+中序遍历值转化为
 *            字符串。然后判断在HashMap中是否存在该值，如果存在则判断该key对应的value是否为0，不为0则将
 *            该根节点加入到结果集中并且将value置为0，为0否则跳过该节点；如果不存在则将该key加入到HashMap中
 *            并将对应的value值置为1。（注意如果节点在HashMap中存在相同的则该根节点以及其下的所有节点都不需
 *            在进行判断了）
 *            
 *            步骤：
 *              （1）构造两个求根节点中序和前序遍历值的方法，并将返回结果设置为String。
 *              （2）定义一个HashMap和一个queue，前者是用于保存二叉树中所有节点的唯一标识，后者用于
 *                   控制对二叉树根节点的遍历顺序以及一个保存结果集的
 *              （3）使用一个while循环用于对二叉树中所有根节点进行遍历，获取二叉树中唯一标识相同的子树，存放在
 *                   结果集中。
 *           问题：对于value为0的节点，唯一标识符会出错。
 */
public class MyMethodOne {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String,Integer> hashMap=new HashMap<String,Integer>();
        Set<Integer> set=new HashSet<Integer>();  //用于添加叶子节点
        Queue<TreeNode> queue=new LinkedList<TreeNode>();  
        TreeNode tem;                //保存临时的TreeNode
        List<TreeNode> result=new LinkedList<TreeNode>();        
        //初始化队列
        if(root!=null && (root.left!=null || root.right!=null))
        	queue.add(root);        
        //遍历二叉树中所有根结点，找到符合要求的根节点
        while(!queue.isEmpty()) {
        	tem=queue.remove();
        	String key=inorderTraversal(tem)+preorderTraversal(tem); //获取每一个子树的唯一标识
        	if(!hashMap.containsKey(key)) {
        		hashMap.put(key, 1);
        		if(tem.left!=null)queue.add(tem.left);
        		if(tem.right!=null)queue.add(tem.right);
        		continue;
        	}
        	if(hashMap.get(key)==1) {
        		result.add(tem);
        		this.input(tem, hashMap, result);
        		hashMap.put(key, 0);    //value为0代表该根节点已经结果集
        	}
        	
        }
        return result;
    }
    
    /**计算根节点的中序遍历结果*/
    private String inorderTraversal(TreeNode node) {
    	StringBuilder tem=new StringBuilder();
    	if(node.left!=null)
    		tem.append(inorderTraversal(node.left));
    	tem.append(node.val);
    	if(node.right!=null)
    		tem.append(inorderTraversal(node.right));
    	return tem.toString();
    }
    
    /**计算根节点的前序遍历结果*/
    private String preorderTraversal(TreeNode node) {
    	StringBuilder tem=new StringBuilder();
    		tem.append(node.val);
    	if(node.left!=null)
    		tem.append(inorderTraversal(node.left));
    	if(node.right!=null)
    		tem.append(inorderTraversal(node.right));
    	return tem.toString();
    }
    
    /**将进入结果集中的所有节点的子节点加入到结果集中*/
    private void input(TreeNode node,Map<String,Integer> hashMap,List<TreeNode> result) {
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	TreeNode tem;
    	if(node.left!=null)queue.add(node.left);
    	if(node.right!=null)queue.add(node.right);
    	while(!queue.isEmpty()) {
    		tem=queue.remove();
    		String key=inorderTraversal(tem)+preorderTraversal(tem);
    		if(!hashMap.containsKey(key)) {
        		result.add(tem);
        		hashMap.put(key, 0);
        		if(tem.left!=null)queue.add(tem.left);
        		if(tem.right!=null)queue.add(tem.right);
        		continue;
        	}
        	if(hashMap.get(key)==1) {
        		result.add(tem);
        		hashMap.put(key, 0);    //value为0代表该根节点已经结果集
        	}
    	}
    }
}
